package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}21:01
 */
public class LeetCode86 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public ListNode partition(ListNode head, int x) {
        //初始化最小链表以及其的指针
        ListNode minList = new ListNode(0);
        ListNode min = minList;
        //初始化最大链表以及其的指针
        ListNode maxList = new ListNode(0);
        ListNode max = maxList;

        while (head != null){
            if (head.val < x){
                min.next = head;//记录大值链表的头，指针后移一位
                min = head;
            }else {
                max.next = head;
                max = head;
            }
            head = head.next;
        }
        //遍历完成后记得最后一段链表最后节点指向null
        max.next = null;//这里要指向null是因为原始链表中该节点的next可能指向minLink中的节点，造成新的链表循环。
        //两端拼接
        min.next = maxList.next;
        return minList.next;
    }
}
